常见数据结构

栈

class Stack {
  constructor() {
    this.stack = []
  }
  push(item) {
    this.stack.push(item)
  }
  pop() {
    this.stack.pop()
  }
  peek() {
    return this.stack[this.getCount() - 1]
  }
  getCount() {
    return this.stack.length
  }
  isEmpty() {
    return this.getCount() === 0
  }
}

队列

1.单链队列

class Queue {
  constructor() {
    this.queue = []
  }
  enQueue(item) {
    this.queue.push(item)
  }
  deQueue() {
    return this.queue.shift()
  }
  getHeader() {
    return this.queue[0]
  }
  getLength() {
    return this.queue.length
  }
  isEmpty() {
    return this.getLength() === 0
  }
}

链表

1.单向链表

// 单向链表
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkList {
    constructor() {
        // 链表长度
        this.size = 0;
        // 头指针
        this.head = null;
        // 尾节点指针
        this.last = null;
    }
    insert(v, index) {
        // 检查越界
        this.checkIndex(index);
        // 创建节点
        const insertNode = new Node(v);
        // 头部插入
        if (this.size === 0) {
            this.head = insertNode;
            this.last = insertNode;
        } else if (index === this.size) {
            // 尾部插入
            this.last.next = insertNode;
            this.last = insertNode;
        } else {
            // 中间插入
            const prev = this.find(this.head, index - 1, 0);
            const next = prev.next;
            prev.next = insertNode;
            insertNode.next = next;
        }
        this.size++;
    }
    unshift(v) {
        // 创建节点
        let insertNode = new Node(v);
        // 链表为空
        if (this.size === 0) {
            this.last = insertNode;
        } else {
            // 不为空
            insertNode.next = this.head;
        }
        this.head = insertNode;
        this.size++;
        return insertNode;
    }
    push(v) {
        // 创建节点
        let insertNode = new Node(v);
        // 链表为空
        if (this.size === 0) {
            this.head = insertNode;
        } else {
            // 不为空
            this.last.next = insertNode;
        }
        this.last = insertNode;
        this.size++;
        return insertNode;
    }
    removeByIndex(index) {
        // 检查越界
        this.checkIndex(index);
        if (this.isEmpty() || index === this.size) throw new Error('Index error');
        let removeNode = null;
        // 从头部删除
        if (index === 0) {
            removeNode = this.head;
            this.head = this.head.next;
        } else if (index === this.size - 1) {
            // 从尾部删除
            removeNode = this.last;
            const prev = this.find(this.head, index - 1, 0);
            prev.next = null;
            this.last = prev;
        } else {
            const prev = this.find(this.head, index - 1, 0);
            removeNode = prev.next;
            prev.next = prev.next.next;
        }
        this.size--;
        return removeNode;
    }
    find(head, index, currentIndex) {
        if (index === currentIndex) return head;
        return this.find(head.next, index, currentIndex + 1);
    }
    toString() {
        let res = '';
        for (let i = 0; i < this.size; i++) {
            res += this.find(this.head, i, 0).value;
        }
        return res;
    }
    getNode(index) {
        this.checkIndex(index);
        return this.find(this.head, index, 0);
    }
    getSize() {
        return this.size;
    }
    isEmpty() {
        return this.size === 0;
    }
    // 检查边界值
    checkIndex(index) {
        if (typeof index !== 'number' || index < 0 || index > this.size) throw Error('Index error')
    }
}

2.双向链表

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class LinkList {
  constructor() {
    // 链表长度
    this.size = 0;
    // 头指针
    this.head = null;
    // 尾指针
    this.last = null;
  }
  insert(v, index) {
    this.checkIndex(index);
    let insertNode = new Node(v);
    // 头部插入
    if (this.size === 0) {
      this.last = insertNode;
      this.head = insertNode;
    } else if (index === this.size) {
      insertNode.prev = this.last;
      this.last.next = insertNode;
      this.last = insertNode;
    } else {
      const prev = this.find(this.head, index - 1, 0);
      insertNode.next = prev.next;
      insertNode.prev = prev;
      prev.next.prev = insertNode;
      prev.next = insertNode;
    }
    this.size++;
    return insertNode;
  }
  removeByIndex(index) {
    this.checkIndex(index);
    if (this.isEmpty() || index === this.size) throw new Error('Index error');
    let removeNode = null;
    // 头部删除
    if (index === 0) {
      removeNode = this.head;
      this.head = this.head.next;
      this.head.prev = null;
    } else if (index === this.size - 1) {
      // 尾部删除
      removeNode = this.last;
      this.last = this.last.prev;
      this.last.next = null;
    } else {
      removeNode = this.find(this.head, index, 0);
      const prev = removeNode.prev;
      const next = removeNode.next;
      prev.next = next;
      next.prev = prev;
    }
    this.size--;
    return removeNode;
  }
  unshift(v) {
    // 创建节点
    let insertNode = new Node(v);
    // 链表为空
    if (this.size === 0) {
      this.last = insertNode;
    } else {
      insertNode.next = this.head;
      this.head.prev = insertNode;
    }
    this.head = insertNode;
    this.size++;
    return insertNode;
  }
  push(v) {
    // 创建节点
    let insertNode = new Node(v);
    // 链表为空
    if (this.size === 0) {
      this.head = insertNode;
    } else {
      insertNode.prev = this.last;
      this.last.next = insertNode;
    }
    this.last = insertNode;
    this.size++;
    return insertNode;
  }
  toString() {
    let res = '';
    for (let i = 0; i < this.size; i++) {
      res += this.find(this.head, i, 0).value;
    }
    return res;
  }
  getNode(index) {
    this.checkIndex(index);
    return this.find(this.head, index, 0);
  }
  find(head, index, currentIndex) {
    if (index === currentIndex) return head;
    return this.find(head.next, index, currentIndex + 1);
  }
  getSize() {
    return this.size;
  }
  isEmpty() {
    return this.size === 0;
  }
  checkIndex(index) {
    if (index < 0 || index > this.size) throw new Error('Index error');
  }
}

树

二叉树

lass TreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

// 构建二叉树
function createBinaryTree(arr) {
  let node = null;
  if (arr == null || arr.length === 0) return;
  let data = arr.shift();
  if (data != null) {
    node = new TreeNode(data);
    node.left = createBinaryTree(arr);
    node.right = createBinaryTree(arr);
  }
  return node;
}

深度优先遍历

// 先序遍历
function preOrderTraveral(node) {
  if (node == null) return;
  console.log(node.data);
  preOrderTraveral(node.left);
  preOrderTraveral(node.right);
}

// 中序遍历
function inOrderTraveral(node) {
  if (node == null) return;
  inOrderTraveral(node.left);
  console.log(node.data);
  inOrderTraveral(node.right);
}

// 后序遍历
function postOrderTraveral(node) {
  if (node == null) return;
  postOrderTraveral(node.left)
  postOrderTraveral(node.right)
  console.log(node.data);
}

非递归遍历

// 先序遍历
function preOrderTraveral(node) {
  if (node == null) return;
  let stack = [];
  // push根节点
  stack.push(node);
  while(stack.length > 0) {
    // 弹出栈顶元素
    node = stack.pop();
    console.log(node.data);
    
    // 注意栈后进后先出
    if (node.right) {
        stack.push(node.right);
    }
    
    if (node.left) {
        stack.push(node.left);
    }
  }
}

// 中序遍历
function inOrderTraveral(node) {
  if (node == null) return;
  let stack = [];
  
  while(stack > 0 || node) {
    if (node) {
        stack.push(node);
        node = node.left;
    } else {
        node = stack.pop();
        console.log(nonde.data);
        node = node.right;
    }
  } 
}

// 后序遍历
function postOrderTraveral(node) {
    if (node) {
        let stack1 = [];
        let stack2 = [];
        while(stack1.length > 0) {
          node = stack1.pop();
          stack2.push(node);
          if (node.left) {
            stack1.push(node.left);
          }
          if (node.right) {
            stack1.push(node.right);
          }
        }
        while(stack2.length > 0) {
          console.log(stack2.pop().data);
        }
    }
}

广度优先遍历

function levelOrderTraveral(node) {
    let queue = [];
    queue.push(node);
    while(queue.length > 0) {
        queue = queue.shift();
        console.log(node.data);
        if (node.left) {
            queue.push(node.left);
        }
        if (node.right) {
            queue.push(node.right);
        }
    }
}

树的最大深度

function maxDepth(root) {
    if (!root) return;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

字典（前缀）树

class Node {
  constructor() {
    this.son = [];
    this.val = null;
    this.isEnd = false;
    this.num = 1;
  }
}

class TrieNode {
  constructor() {
    this.root = new Node();
  }
  insert(str) {
    if (str == null || str.length === 0) return;
    let node = this.root;
    let letters = [...str];
    for (let i = 0; i < letters.length; i++) {
      let pos = letters[i].charCodeAt() - 'a'.charCodeAt();
      if (node.son[pos] == null) {
        node.son[pos] = new Node();
        node.son[pos].val = letters[i];
      } else {
        node.son[pos].num++;
      }
      node = node.son[pos];
    }
    node.isEnd = true;
  }
  search(str) {
    if (str == null || str.length === 0) return;
    let node = this.root;
    let letters = [...str];
    for (let i = 0; i < str.length; i++) {
      let pos = letters[i].charCodeAt() - 'a'.charCodeAt();
      if (node.son[pos] != null) {
        node = node.son[pos];
      } else {
        return false;
      }
    }
    //走到这一步，表明可能完全匹配，也可能部分匹配，如果最后一个字符节点为末端节点，则是完全匹配，否则是部分匹配
    return node.isEnd;
  }
}

let trie = new TrieNode();
trie.insert('abc');
trie.insert('abd');
trie.insert('apl');
console.log(JSON.stringify(trie));
console.log(trie.search('abc'));